/*
题目描述：一个排序数组，经过将前面一段移动到数组的后面，修改后的数组成为旋转数组。给定一个旋转数组，找出数组的最小值
分析：
可以将旋转数组看成两个升序的排序数组，于是可以考虑二分查找。
定义两个指针p1和p2，初始状态p1指向前一段数组的第一个位置，p2指向后一段数组的最后一个位置，最小元素位于后一段数组的第一个位置。
通过二分法移动p1和p2，使得最后的结果为p1指向第一段数组的最后一个位置，怕p2指向第二段数组的第一个位置，返回最小值。
值得注意的是，left，right，mid指向的数字是相同的情况下，我们是无法判断mid指向的值是属于左半段还是右半段，这个时候，我们只能通过进行顺序查找。
方法：
1. 扫描一遍
2.
 */
public class E11 {
    public static void main(String[] args){
        int[] num1 = {3,4,5,1,2};
        int[] num2 = {1,0,1,1,1};
        int[] num3 = {4,7,9,12,56,-3,-2,-1,0};

        int res1 = Min(num1);
        int res2 = Min(num2);
        int res3 = Min(num3);

        System.out.println("res1 = " + res1);
        System.out.println("res2 = " + res2);
        System.out.println("res3 = " + res3);
    }
    public static int Min(int[] num){
        if(num == null || num.length <= 0){
            System.exit(-1);
        }
        int left = 0;
        int right = num.length - 1;
        int mid = left;
        while(num[left] >= num[right]){
            if(right - left == 1){
                mid = right;
                break;
            }
            mid = left + (right - left) / 2;
            if(num[left] == num[mid] && num[left] == num[right]){
                return MinInOrder(num, left, right);
            }
            if(num[mid] >= num[left]){
                left = mid;
            }
            else if(num[mid] <= num[right]){
                right = mid;
            }
        }
        return num[mid];
    }
    public static int MinInOrder(int[] num, int left, int right){
        int res = num[left];
        for(int i = left + 1; i <= right; i++){
            if(num[i] < res){
                res = num[i];
            }
        }
        return res;
    }
}
/*
res1 = 1
res2 = 0
res3 = -3
 */